The present invention relates to ad hoc networks.
Wireless networks are becoming increasingly popular in both office and home settings. Wireless networks are favored over wireline networks for many reasons. For example, they are easier to install in existing buildings and they provide users with the ability to move around while using their personal digital assistants (PDAs), laptops, etc. and still remain connected to the Internet and to each other.
One approach to wireless networking is via the use of a base station. In this approach, all nodes in the network communicate directly with the base station, which redirects the traffic to the destination node. There are several disadvantages to this approach. For example, a preexisting base-station-based infrastructure is not always available. In addition, the various devices in the network might be battery operated, and the desire to limit power consumption in such devices precludes long range communication.
Ad hoc networking can avoid such disadvantages. In an ad hoc network, the various devices, or “nodes,” communicate directly which each other, on a peer-to-peer basis, over communication routes that are not fixed or predetermined. For example, the communication path between a pair of mobile devices in the network, such as two co-workers' PDAs, may initially be a direct, line-of-sight path when the devices are relatively close to one another. We refer to such a path as a local link. As the users move about the work facility, however, the broadcast power of the devices and/or obstructions to radio-frequency transmission within the environment may preclude such local-link communications. In that case, the communication route between the two PDAs may become a multi-link path involving a third device, such as a third employee's PDA, as an intermediary relay point.
One approach to routing messages in an ad hoc network is referred to as flooding. An originating node generates a message identifying the desired destination node. All nodes that receive the message rebroadcast it until, it is hoped, the desired destination node ultimately receives it. This approach is quite inefficient because of the inherent redundancy of the communications, giving rise to many message collisions, which in turn gives rise to many rebroadcasts and consumes the battery power of mobile devices that have only limited amounts of battery power to start with. A more refined approach involves each node learning the identities of the nodes with which it can communicate—its so-called neighbors—by exchanging messages designed for that purpose. The information generated at each node about its neighbors is propagated around the network so that, ultimately, an originating node is possessed of enough information so as to be able to identify some path through the network between itself and a desired destination and can address messages accordingly.